package com.company.xiecheng;

import java.util.*;

public class Main {

    public static class LRU1<K, V> {
        private final int MAX_CACHE_SIZE;
        private final float DEFAULT_LOAD_FACTORY = 0.75f;

        LinkedHashMap<K, V> map;

        List<Value<K, V>> list = new ArrayList<>();

        public LRU1(int cacheSize) {
            MAX_CACHE_SIZE = cacheSize;
            int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
            map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > MAX_CACHE_SIZE;
                }
            };
            list = new ArrayList<>();
        }

        public synchronized void put(K key, V value) {
            if(map.size() >= MAX_CACHE_SIZE){
                Collections.sort(list);
                Value<K, V> v = list.get(0);
                K k = v.key;
                map.remove(k);
            }
            map.put(key, value);
            list.add(new Value<>(key, value, 0));
        }

        public synchronized V get(K key) {
            for(Value<K, V> item: list){
                if(item.key == key){
                    item.freq++;
                }
            }
            return map.get(key);
        }

        public synchronized void remove(K key) {
            map.remove(key);
        }

        public synchronized Set<Map.Entry<K, V>> getAll() {
            return map.entrySet();
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            for (Map.Entry<K, V> entry : map.entrySet()) {
                stringBuilder.append(String.format("%s: %s  ", entry.getKey(), entry.getValue()));
            }
            return stringBuilder.toString();
        }

        public boolean containsKey(K key){
            return map.containsKey(key);
        }

        static class Value<K, V> implements Comparable{
            K key;
            V value;
            int freq;
            public Value(K key, V value, int freq) {
                this.key = key;
                this.value = value;
                this.freq = freq;
            }

            @Override
            public int compareTo(Object o) {
                Value v = (Value) o;
                return this.freq - v.freq;
            }
        }
    }

    //测试

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        LRU1<Integer, Integer> cache = new LRU1<>(n);
        StringBuilder builder = new StringBuilder();
        String next = null;
        while ((next = sc.nextLine()) != null && !"".equals(next)){
            builder.append(next);
        }
        String[] strs = builder.toString().split("\n");
        for(int i = 0; i < strs.length; i++){
            String line = strs[i];
            String[] ops = line.split(" ");
            if("p".equals(ops[0])){
                int key = Integer.parseInt(ops[1]);
                int value = Integer.parseInt(ops[2]);
                cache.put(key, value);
            }else if("g".equals(ops[0])){
                int key = Integer.parseInt(ops[1]);
                if(cache.containsKey(key)){
                    System.out.println(cache.get(key));
                }else{
                    System.out.println(-1);
                }
            }
        }
    }
}